#include"graph.h"

const int base = 1e6;
void Test_Dijkstra()
{
	int n = 0;
	printf("请输入节点个数：\n");
	scanf("%d", &n);
	int m = 0;
	printf("请输入边的个数：\n");
	scanf("%d", &m);
	int start = 0, end = 0;
	printf("请输入要求的最短路径的起点和终点：\n");
	scanf("%d%d", &start,&end);

	int** road = (int**)malloc(sizeof(int*) * m);//保存边数
	if (NULL == road)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	for (int i = 0; i < m; ++i)//给一维数组开空间
	{
		road[i] = (int*)malloc(sizeof(int) * 4);
		if (NULL == road[i])
		{
			printf("malloc failed\n");
			exit(-1);
		}
	}

	printf("输入%d个弧的起点、终点、长度(km)、以及平均速度(km/h)：\n", m);
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < 4; ++j)
			scanf("%d", &road[i][j]);


	

	RN* r1 = Dijkstra2(n,m,road, start, end);
	//首先输出最短路径
	printf("%d->%d的最短长度路径为：", start, end);
	PrintLength(r1->pre, end);
	printf("\n");
	printf("最短路径长度为：%dkm\n", r1->dist[end]);
	printf("dist长度表为：\n");
	for (int i = 0; i < n; ++i)
		printf("S%d->S%d: %dkm ", start, i, r1->dist[i]);
	printf("\n");
	for (int i = 0; i < m; ++i)
	{
		  double t = 1.0 * road[i][2] / road[i][3];
		  printf("S%d->S%d的平均时间为：%lfmin\n", road[i][0], road[i][1], t*60);
		  road[i][2] = t * base;
	}
	printf("\n");
	RN* r2 = Dijkstra2(n,m,road, start, end);
	//首先输出最短路径
	printf("S%d->S%d的最短时间路径为：", start, end);
	PrintLength(r2->pre, end);
	printf("\n");
	printf("最短时间为%lfmin\n", 1.0*r2->dist[end]/base*60);
	printf("dist时间表为：\n");
	for (int i = 0; i < n; ++i)
		printf("S%d->S%d: %lfmin ", start,i,1.0*(r2->dist[i])/base*60);
	
	//释放空间，防止内存泄漏
	free(r1->dist);
	r1->dist = NULL;
	free(r1->pre);
	r1->pre = NULL;
    free(r1);

	free(r2->dist);
	r2->dist = NULL;
	free(r2->pre);
	r2->pre = NULL;
    free(r2);
}

int main()
{
	Test_Dijkstra();
	return 0;
}